// 实现前缀树数据结构的相关类Tries类
// 思路， 前缀树（字典树）
// 前缀树是一颗多叉树，其中每个节点包含指向子节点的指针数组children，以及布尔变量isEnd，children用于存储当前字符节点，一般长度为所含字符种类个数，可以使用
// 哈希表代替指针数组，isEnd用于判断该节点是否为字符串的结尾

function Node() {
    this.children = new Map()
    this.isEnd = false
}

function Trie() {
    this.root = new Node()
}

Trie.prototype.insert = function (word) {
    let cur = this.root
    for (const item of word) {
        if (!cur.children.has(item)) {
            cur.children.set(item, new Node())
        }
        cur = cur.children.get(item)
    }
    cur.isEnd = true
}

Trie.prototype.search = function (word) {
    let cur = this.root
    for (const item of word) {
        if (!cur.children.has(item)) {
            return false
        }
        cur = cur.children.get(item)
    }
    return cur && cur.isEnd
}

Trie.prototype.startsWith = function (prefix) {
    let cur = this.root
    for (const item of prefix) {
        if (!cur.children.has(item)) {
            return false
        }
        cur = cur.children.get(item)
    }
    return !!cur
}

const trie = new Trie()
console.log(trie.insert('apple'));
console.log(trie.insert('abs'));
console.log(trie.search('apple'))
console.log(trie.startsWith('apple'))